#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/* 尾递归 */
int tailRecur(int n, int res) {
    // 终止条件
    if (n == 0)
        return res;
    // 尾递归调用
    return tailRecur(n - 1, res + n);
}

/* 递归 */
int recur(int n) {
    int sum = 0;
    if(n == 0)
        return sum;
    sum = recur(n-1);
    return n+sum;
}
/*0 1 1 2 3 5 8 13*/
/* 斐波那契数列：递归 */
int fib(int n) {
    // 终止条件 f(1) = 0, f(2) = 1
    if (n == 1 || n == 2)
        return n - 1;
    // 递归调用 f(n) = f(n-1) + f(n-2)
    int res = fib(n - 1) + fib(n - 2);
    // 返回结果 f(n)
    return res;
}


int binarySearchLCRO(int *nums, int len, int target) 
{
    int p = 0;
    int q = len - 1;
    while(p <= q)
    {
        int m = (p + q)/2 ;
        if(nums[m] < target)
        {
            p = m+1;
        }
        if(nums[m] > target)
        {
            q = m-1;
        }
        if(nums[m] == target)
        {
            return m+1;
        }
    }


}

/* 
// 时间复杂度高：数组的插入和删除的平均时间复杂度均为 O(n)，其中 n为数组长度。
// 丢失元素：由于数组的长度不可变，因此在插入元素后，超出数组长度范围的元素会丢失。
// 内存浪费：我们可以初始化一个比较长的数组，只用前面一部分，这样在插入数据时，丢失的末尾元素都是“无意义”的，但这样做也会造成部分内存空间的浪费。
*/
//0 1 2 3 index 4 5 6
/* 在数组的索引 index 处插入元素 num */
void insert(int *nums, int size, int num, int index) {
    // 把索引 index 以及之后的所有元素向后移动一位
    for(int i = size -1 ; i > index ; i--)
    {
        nums[i] = nums[i-1];// 现在的位置让给你的前一位，你就往后挪啦
    }
    nums[index] = num;
}

void removeItem(int *nums, int size, int index) 
{
    for(int i = size -1 ; i > index ; i--)
    {
        nums[i] = nums[i+1];// 现在的位置让给你的后一位，你就往前挪啦
    }

}


char* reversePrefix(char* word, char ch) {
    int i = 0;
    int j ;
    int len = strlen(word);
    char *newword = malloc(len*(sizeof(char)));
    for(i = 0; i<len; i++)
    {
        if(word[i]==ch)
        {
            for(j=0; j<=i; j++)
            {
                newword[j]=word[i-j];
            }
            for(j=i+1; j<len; j++)
            {
                newword[j]=word[j];
            }
            return newword;
        }
    }
    return NULL;
}

int main()
{
    int arr[19] = {1,2,3,4,56,64,43,2,4,5,3,432,34,4,5,6,20,234,23};
    //insert(arr, 19, 10, 6);
    //int n = binarySearchLCRO(arr , 19, 43);
    //int n = recur(200);
    //int n = tailRecur(200 , 10000);
    volatile char *b = "abcdefg";
    char *a = reversePrefix(b , 'd');
    for(int i = 0; i < 7 ;i++)
    {
        printf("%d\n",a[i]);

    }
    //printf("%d\n",n);
}